<?php

namespace App\Libs;

/**
 * 将公会和礼物(暂定)构建成trie树，方便根据名字查找, 如果数据量多请使用专业的搜索引擎，比如ElasticSearch
 * use:
 * $obj = new App\Libs\TrieTree();
 * $obj->addWords($keyword, $name); $keyword表示ID值，$name表示公会或礼物的名字
 * $obj->getTargetArray(); 表示最终构建的trie树, 请自行存储
 * 需要查找的时候，需要先
 * $obj->setTargetArray(树结构);
 * $obj->getAllMatches(xxx); 会查找以 xxx 开头的所有 id和name
 */
class TrieTree
{
    /**
     * 用数组来存储trie树
     * @var array
     */
    private $targetArray = [];

    /**
     * 分割文本(注意ascii占1个字节, unicode...)
     * @param string $str 要分隔的字符串
     * @return string[]|false
     */
    protected function splitStr(string $str)
    {
        // /u表示按unicode编码方式分割字符串
        // 例如: "abc你我他" 会被切割为["a", "b", "c", "你", "我", "他"]
        return preg_split("//u", $str, -1, PREG_SPLIT_NO_EMPTY);
    }

    /**
     * 构建Trie树
     * @param string $keyword end的值
     * @param string $word 字符串
     */
    public function addWords(string $keyword, string $word)
    {
        $wordArr = $this->splitStr($word);
        $curNode = &$this->targetArray;
        $prefix = '';//用于显示name
        foreach ($wordArr as $char) {
            $prefix .= $char;
            if (!isset($curNode)) {
                $curNode[$char] = [];
            }

            $curNode = &$curNode[$char];
        }

        // 标记到达当前节点完整路径为"敏感词"
        $curNode['end'] = $keyword;
        $curNode['name'] = $prefix;
    }

    /**
     * 查找所有的匹配项
     * @param string $strPrefix
     * @return array
     */
    public function getAllMatches(string $strPrefix): array
    {
        $result = [];
        $strPrefix = trim($strPrefix);
        if ($strPrefix == '') {
            return $result;
        }

        $strArr = $this->splitStr($strPrefix);//解析字符串
        $length = count($strArr);
        $curNode = $this->targetArray[$strArr[0]];
        if (empty($curNode)) {//首字符不存在, 直接返回
            return $result;
        }

        for ($i = 1; $i < $length; $i++) {
            $char = $strArr[$i];
            $curNode = $curNode[$char];
            if (empty($curNode)) {
                return $result;
            }
        }

        $treeArrNode = [[0 => $curNode]];
        while (count($treeArrNode) > 0) {
            $element = array_shift($treeArrNode);
            $node = array_keys($element)[0];//当前节点的字符
            $element = $element[$node];
            if (isset($element['end'])) {
                $result[] = ['id' => $element['end'], 'name' => $element['name']];
                unset($element['end'], $element['name']);
            }

            if ($element) {
                if (count($element) >= 2) {
                    foreach ($element as $key => $item) {
                        array_push($treeArrNode, [$key => $item]);
                    }
                } else {
                    array_push($treeArrNode, $element);
                }
            }
        }

        return $result;
    }

    /**
     * 获取最终的trie树
     * @return array
     */
    public function getTargetArray(): array
    {
        return $this->targetArray;
    }

    /**
     * 设置targetArray
     * @param string $jsonTargetArray
     */
    public function setTargetArray(string $jsonTargetArray)
    {
        $this->targetArray = json_decode($jsonTargetArray, true);
    }
}
